package com.ohc.leetcode.链表;

import com.sun.org.apache.bcel.internal.generic.NEW;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 2022年6月17日09:07:31
 */
public class 回文链表234 {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static boolean isPalindrome(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode temp = head;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }

        while (!stack.isEmpty()) {
            ListNode popNode = stack.pop();
            if (!(popNode.val == head.val)) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    /**
     * 他人方法西也许
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome2(ListNode head) {
        List<Integer> list = new ArrayList<>();
        ListNode temp = head;
        while (temp != null) {
            list.add(temp.val);
            temp = temp.next;
        }
        int left = 0;
        int right = list.size() - 1;
        while (left < right) {
            if (!(list.get(left)).equals(list.get(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        ListNode listNode4 = new ListNode(1, null);
        ListNode listNode3 = new ListNode(2, listNode4);
        ListNode listNode2 = new ListNode(2, listNode3);
        ListNode listNode1 = new ListNode(1, listNode2);
        boolean flag = isPalindrome2(listNode1);
        System.out.println("flag = " + flag);
    }
}
